package org.example;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

// 二维数组的花式遍历技巧
// https://labuladong.online/algo/practice-in-action/2d-array-traversal-summary/
public class TwoDimensionalArray {
    // 顺/逆时针旋转矩阵
    // 48. 旋转图像
    // 给定一个 n × n 的二维矩阵 matrix 表示一个图像。请你将图像顺时针旋转 90 度。
    // 你必须在 原地 旋转图像，这意味着你需要直接修改输入的二维矩阵。请不要 使用另一个矩阵来旋转图像。
    // 输入：matrix = [[1,2,3],[4,5,6],[7,8,9]]
    // 输出：[[7,4,1],[8,5,2],[9,6,3]]

    // 思路：
    // 1. 我们可以现将nxn矩阵matrix按照左上到右下的对角线进行镜像对称；
    // 2. 然后在对矩阵的每一行进行反转；
    // 3. 发现结果就是matrix顺时针旋转90度的结果。
    static class Rotate {
        // 将二维矩阵原地[顺时针]旋转90度
        public void rotate(int[][] matrix) {
            int n = matrix.length;
            // 先沿对角线镜像对称二维矩阵
            for (int i = 0; i < n; i++) {
                for (int j = i; j < n; j++) {
                    // swap(matrix[i][j], matrix[j][i]);
                    int temp = matrix[i][j];
                    matrix[i][j] = matrix[j][i];
                    matrix[j][i] = temp;
                }
            }
            // 然后反转二维矩阵的每一行
            for (int[] row : matrix) {
                reverse(row);
            }
        }

        // 反转一维数组
        void reverse(int[] arr) {
            int i = 0;
            int j = arr.length - 1;
            while (j > i) {
                // swap(arr[i], arr[j]);
                int temp = arr[i];
                arr[i] = arr[j];
                arr[j] = temp;
                i++;
                j--;
            }
        }

        // 将二维矩阵原地[逆时针]旋转90度
        public void rotate1(int[][] matrix) {
            int n = matrix.length;
            // 沿左下到右上的对角线镜像对称二维矩阵
            for (int i = 0; i < n; i++) {
                for (int j = n - i; j < n; j++) {
                    // swap(matrix[i][j], matrix[n-j-1][n-i-1])
                    int temp = matrix[i][j];
                    matrix[i][j] = matrix[n - j - 1][n - i - 1];
                    matrix[n - j - 1][n - i - 1] = temp;
                }
            }
            // 然后反转二维矩阵的每一行
            for (int[] row : matrix) {
                reverse(row);
            }
        }
    }


    // 矩阵的螺旋遍历
    // 54. 螺旋矩阵
    // 给你一个 m 行 n 列的矩阵 matrix ，请按照 顺时针螺旋顺序 ，返回矩阵中的所有元素。
    // 输入：matrix = [[1,2,3],[4,5,6],[7,8,9]]
    // 输出：[1,2,3,6,9,8,7,4,5]
    static class SpiralOrder {
        // 方法一
        public List<Integer> spiralOrder(int[][] matrix) {
            int m = matrix.length;
            int n = matrix[0].length;
            int upper_bound = 0;
            int lower_bound = m - 1;
            int left_bound = 0;
            int right_bound = n - 1;
            List<Integer> res = new LinkedList<>();
            // res.size = m * n;
            while (res.size() < m * n) {
                if (upper_bound <= lower_bound) {
                    // 在顶部从左向右遍历(实际遍历的列)
                    for (int j = left_bound; j <= right_bound; j++) {
                        res.add(matrix[upper_bound][j]);
                    }
                    // 上边界下移
                    upper_bound++;
                }
                if (left_bound <= right_bound) {
                    // 在右侧从上向下遍历（实际遍历的行）
                    for (int i = upper_bound; i <= lower_bound; i++) {
                        res.add(matrix[i][right_bound]);
                    }
                    // 右边界左移
                    right_bound--;
                }
                if (upper_bound <= lower_bound) {
                    // 在底部从右向左遍历
                    for (int j = right_bound; j >= left_bound; j--) {
                        res.add(matrix[lower_bound][j]);
                    }
                    // 下边界上移
                    lower_bound--;
                }
                if (left_bound <= right_bound) {
                    // 在左侧从下向上遍历
                    for (int i = lower_bound; i >= upper_bound; i--) {
                        res.add(matrix[i][left_bound]);
                    }
                    // 左边界右移
                    left_bound++;
                }
            }
            return res;
        }

        // 方法二：int[][] directions = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
        // # 表示上、下、左、右、左上、右上、左下、右下八个方向的偏移量数组
        // offsets = [(-1, 0), (1, 0), (0, -1), (0, 1), (-1, -1), (-1, 1), (1, -1), (1, 1)]
        // (-1, 0)：行索引减 1，列索引不变，即向上移动。
        // (1, 0)：行索引加 1，列索引不变，即向下移动。
        // (0, -1)：行索引不变，列索引减 1，即向左移动。
        // (0, 1)：行索引不变，列索引加 1，即向右移动。
        // (-1, -1)：行索引减 1，列索引减 1，即向左上方移动。
        // (-1, 1)：行索引减 1，列索引加 1，即向右上方移动。
        // (1, -1)：行索引加 1，列索引减 1，即向左下方移动。
        // (1, 1)：行索引加 1，列索引加 1，即向右下方移动。
        public List<Integer> spiralOrder1(int[][] matrix) {
            List<Integer> res = new ArrayList<>();
            if (matrix == null || matrix.length == 0 || matrix[0].length == 0){
                return res;
            }
            int rows = matrix.length;
            int columns = matrix[0].length;
            boolean[][] visited = new boolean[rows][columns];
            int total = rows * columns;
            int row = 0;
            int column = 0;
            int[][] directions = {{0, 1},{1, 0},{0, -1},{-1, 0}};
            int directionIndex = 0;
            for(int i = 0; i < total; i++){
                res.add(matrix[row][column]);
                visited[row][column] = true;
                int nextRow = row + directions[directionIndex][0];
                int nextColum = column + directions[directionIndex][1];
                if (nextRow < 0 || nextRow >= rows || nextColum < 0 || nextColum >= columns || visited[nextRow][nextColum]){
                    directionIndex = (directionIndex + 1) % 4;
                }
                row += directions[directionIndex][0];
                column += directions[directionIndex][1];
            }
            return res;
        }

        public static void main(String[] args) {
            int[][] matrix = {{1,2,3}, {4,5,6}, {7,8,9}};
            new SpiralOrder().spiralOrder(matrix);
        }
    }

    // 59. 螺旋矩阵 II
    // 给你一个正整数 n ，生成一个包含 1 到 n2 所有元素，且元素按顺时针顺序螺旋排列的 n x n 正方形矩阵 matrix 。
    // 输入：n = 3
    // 输出：[[1,2,3],[8,9,4],[7,6,5]]
    static class GenerateMatrix{
        public int[][] generateMatrix(int n) {
            int[][] matrix = new int[n][n];
            int upper_bound = 0;
            int lower_bound = n-1;
            int left_bound = 0;
            int right_bound = n - 1;
            // 需要填入矩阵的数字
            int num = 1;
            while(num <= n * n){
                if (upper_bound <= lower_bound){
                    // 在顶部从左向右遍历
                    for(int j = left_bound; j <= right_bound; j++){
                        matrix[upper_bound][j] = num++;
                    }
                    // 上边界下移
                    upper_bound++;
                }
                if (left_bound <= right_bound){
                    // 在右侧从上向下遍历
                    for(int i = upper_bound; i <= lower_bound; i++){
                        matrix[i][right_bound] = num++;
                    }
                    // 右边界左移
                    right_bound--;
                }
                if (upper_bound <= lower_bound){
                    // 在底部从右向左遍历
                    for (int j = right_bound; left_bound <= j; j--){
                        matrix[lower_bound][j] = num++;
                    }
                    // 下边界上移
                    lower_bound--;
                }
                if (left_bound <= right_bound){
                    // 在左侧从下向上遍历
                    for(int i = lower_bound; upper_bound <= i; i--){
                        matrix[i][left_bound] = num++;
                    }
                    // 左边界右移
                    left_bound++;
                }
            }
            return matrix;
        }
    }
}
